package com.dyz.swordFingerOffer;

import java.util.HashMap;

public class RandomListNode35 {
    public HashMap<RandomListNode, RandomListNode> map = new HashMap<>();

    //解题1
    public RandomListNode Clone1(RandomListNode pHead) {
         if (pHead==null){
             return null;
         }
         if(map.containsKey(pHead)){
             return map.get(pHead);
         }
         RandomListNode tmpNode = new RandomListNode(pHead.label);
         map.put(pHead, tmpNode);
         tmpNode.next = Clone1(pHead.next);
         tmpNode.random = Clone1(pHead.random);
         return tmpNode;
    }
    //解题2
    public RandomListNode Clone(RandomListNode pHead) {
        RandomListNode cur = pHead;
        //
        while(cur!=null){
            //去创建新的链表中的节点元素和原链表节点元素与元素之间的映射关系
            RandomListNode temp = new RandomListNode(cur.label);
            map.put(cur, temp);
            cur = cur.next;
        }

        cur  = pHead;
        //去创建新链表中各个节点的结构关系（根据原链表的节点的结构关系）
        while(cur!=null){
            RandomListNode node = map.get(cur);
            node.next = map.get(cur.next);
            node.random = map.get(cur.random);
            cur = cur.next;
        }
        return map.getOrDefault(pHead, null);
    }
}
class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;

    RandomListNode(int label) {
        this.label = label;
    }
}